package demo.practice.uf;

import java.util.*;

public class P721 {


    public List<List<String>> accountsMerge(List<List<String>> accounts) {


        UF uf = new UF();
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size() - 1; i++) {
                uf.join(account.get(i), name, account.get(i + 1), name);
            }
        }

        List<List<String>> res = new ArrayList<>();
        for (Map.Entry<String, Set<String>> en : uf.allemails.entrySet()) {
            List<String> r = new ArrayList<>();
            r.add(uf.namemap.get(en.getKey()));
            r.addAll(en.getValue());
            res.add(r);
        }

        return res;
    }

    class UF {
        public Map<String, String> parent = new HashMap<>();
        public Map<String, Integer> rank = new HashMap<>();
        public Map<String, Set<String>> allemails = new HashMap<>();
        public Map<String, String> namemap = new HashMap<>();

        //Set<>
        public UF() {

        }

        public String findP(String a) {
            while (!a.equals(parent.get(a))) {
                if (parent.get(a) == null)
                    return null;
                a = parent.get(a);
            }
            return a;
        }

        public void join(String a, String na, String b, String nb) {
            if (a == null || b == null) {
                return;//或者抛出异常
            }

            String pa = findP(a);
            if (pa == null) {
                parent.put(a, a);
                rank.put(a, 1);
                Set<String> emails = new HashSet<>();
                emails.add(a);
                allemails.put(a, emails);
                namemap.put(a, na);
                join(a, na, b, nb);
                return;
            }
            String pb = findP(b);
            if (pb == null) {
                parent.put(b, b);
                rank.put(b, 1);
                Set<String> emails = new HashSet<>();
                emails.add(b);
                allemails.put(b, emails);
                namemap.put(b, nb);
                join(a, na, b, nb);
                return;
            }
            if (!pa.equals(pb)) {
                if (rank.get(pa) > rank.get(pb)) {
                    //矮的接到高的    pb合到pa上
                    parent.put(pb, pa);
                    namemap.put(pb, namemap.get(pa));
                    Set<String> eb = allemails.get(pb);
                    allemails.get(pa).addAll(eb);
                    allemails.remove(pb);
                } else if (rank.get(pa) < rank.get(pb)) {
                    parent.put(pa, pb);
                    namemap.put(pa, namemap.get(pb));
                    Set<String> ea = allemails.get(pa);
                    allemails.get(pb).addAll(ea);
                    allemails.remove(pa);

                } else {
                    parent.put(pb, pa);
                    namemap.put(pb, namemap.get(pa));
                    Set<String> eb = allemails.get(pb);
                    allemails.get(pa).addAll(eb);
                    allemails.remove(pb);
                    rank.put(pa, rank.get(pa) + 1);
                }
            }
        }
    }
}
